import tester.*;
import tester.Tester;
//import java.util.Scanner;
//import java.util.Stack;
import java.util.*;

class Examples {
  Examples() {}
  Graph<String, String, Integer> cityGraph = new Graph<String, String, Integer>("United States");

  // Boston is connected to Tucson, New York, and Chicago
  INode<String, Integer> boston = new Node<String, Integer>("Boston, MA");
  // Tucson is connected to Boston and Chicago
  INode<String, Integer> tucson = new Node<String, Integer>("Tucson, AZ");
  // New York is connected to Boston and Tucson
  INode<String, Integer> newyork = new Node<String, Integer>("New York, NY");
  // Chicago is connected to New York and Tucson
  INode<String, Integer> chicago = new Node<String, Integer>("Chicago, IL");
  // Miami is on its own network with Tallahasse
  INode<String, Integer> miami = new Node<String, Integer>("Miami, FL");
  // Tallahasse is on its own network with Miami
  INode<String, Integer> tallahasse = new Node<String, Integer>("Tallahasse, FL");

  // All the links leaving from Boston
  ILink<Integer, String> bostonToTucson = new Link<Integer, String>(tucson, new Integer(100));
  ILink<Integer, String> bostonToNewyork = new Link<Integer, String>(newyork, new Integer(10));
  ILink<Integer, String> bostonToChicago = new Link<Integer, String>(chicago, new Integer(50));

  // All the links leaving from Tucson
  ILink<Integer, String> tucsonToBoston = new Link<Integer, String>(boston, 100);
  ILink<Integer, String> tucsonToChicago = new Link<Integer, String>(chicago, 150);

  // All the links leaving from New York
  ILink<Integer, String> newyorkToBoston = new Link<Integer, String>(boston, 10);
  ILink<Integer, String> newyorkToTucson = new Link<Integer, String>(tucson, 200);

  // All the links leaving from Chicago
  ILink<Integer, String> chicagoToNewyork = new Link<Integer, String>(newyork, 50);
  ILink<Integer, String> chicagoToTucson = new Link<Integer, String>(tucson, 100);

  // All the links leaving Miami
  ILink<Integer, String> miamiToTallahasse = new Link<Integer, String>(this.tallahasse, 30);

  // All the links leaving Tallahasse
  ILink<Integer, String> tallahasseToMiami = new Link<Integer, String>(this.miami, 30);

  // Stacks representing a path from one city to another from a DFS
  Stack<INode<String, Integer>> pathBostonTucsonDFS = new Stack<INode<String, Integer>>();
  Stack<INode<String, Integer>> pathTucsonNewyorkDFS = new Stack<INode<String, Integer>>();
  // Stacks representing a path from one city to another from a BFS
  LinkedList<INode<String, Integer>> pathBostonTucsonBFS = new LinkedList<INode<String, Integer>>();
  LinkedList<INode<String, Integer>> pathTucsonNewyorkBFS = new LinkedList<INode<String, Integer>>();

  /* Old paths
    // Some example paths
    Path<String, Integer> pathBostonTucson = new Path<String, Integer>(this.boston, this.tucson);
    Path<String, Integer> pathTucsonNewyork = new Path<String, Integer>(this.tucson, this.newyork);
    // these two are invalid
    Path<String, Integer> pathBostonMiami = new Path<String, Integer>(this.boston, this.miami);
    Path<String, Integer> pathMiamiBoston = new Path<String, Integer>(this.miami, this.boston);
  */

  ///// MORE ADVANCED CITY DATA /////
  // This data uses the city structure, route structure, etc.
  // The following few examples show example Cities, which are used as node information
  // for the nodes, which are parameterized by a City and a Route (routes can be found
  // below).
  Posn tucsonPosn = new Posn(30, 200);
  City tucsonCity = new City("Tucson", "AZ", tucsonPosn);
  INode<City, Route> tucsonNode = new Node<City, Route>(tucsonCity);

  Posn bostonPosn = new Posn(220, 35);
  City bostonCity = new City("Boston", "MA", bostonPosn);
  INode<City, Route> bostonNode = new Node<City, Route>(bostonCity);

  Posn newyorkPosn = new Posn(210, 38);
  City newyorkCity = new City("New York", "NY", newyorkPosn);
  INode<City, Route> newyorkNode = new Node<City, Route>(newyorkCity);

  Posn chicagoPosn = new Posn(170, 30);
  City chicagoCity = new City("Chicago", "IL", chicagoPosn);
  INode<City, Route> chicagoNode = new Node<City, Route>(chicagoCity);

  // ROUTES
  // The following are route objects and their associated links, parameterized by the type
  // of information inside of them, which is a Route object. (the Link represents the
  // mathematical relationship between the two nodes, while the Route class contains specific
  // information about the route. When the links are created, they take two parameters; a
  // Route object with specific information about the route that the links represent, and
  // A Node<City, Route>, which is the destination of the link.
  Route bostonTucsonRoute = new Route("US400", 800, 1.5);
  ILink<Route, City> bostonTucson = new Link<Route, City>(tucsonNode, bostonTucsonRoute);
  Route bostonNewyorkRoute = new Route("US395", 150, 2.8);
  ILink<Route, City> bostonNewyork = new Link<Route, City>(newyorkNode, bostonNewyorkRoute);
  Route bostonChicagoRoute = new Route("US250", 300, 1.0);
  ILink<Route, City> bostonChicago = new Link<Route, City>(chicagoNode, bostonChicagoRoute);

  Route tucsonBostonRoute = new Route("US400", 800, 1.5);
  ILink<Route, City> tucsonBoston = new Link<Route, City>(bostonNode, tucsonBostonRoute);
  Route tucsonChicagoRoute = new Route("US440", 600, 0.9);
  ILink<Route, City> tucsonChicago = new Link<Route, City>(chicagoNode, tucsonChicagoRoute);

  Route newyorkBostonRoute = new Route("US395", 150, 1.3);
  ILink<Route, City> newyorkBoston = new Link<Route, City>(bostonNode, newyorkBostonRoute);
  Route newyorkChicagoRoute = new Route("US270", 200, 1.4);
  ILink<Route, City> newyorkChicago = new Link<Route, City>(chicagoNode, newyorkChicagoRoute);

  Route chicagoNewyorkRoute = new Route("US270", 200, 1.7);
  ILink<Route, City> chicagoNewyork = new Link<Route, City>(newyorkNode, chicagoNewyorkRoute);
  Route chicagoTucsonRoute = new Route("US440", 600, 0.8);
  ILink<Route, City> chicagoTucson = new Link<Route, City>(tucsonNode, chicagoTucsonRoute);

  // The graph structure which will contain all of our example data. It is parameterized by
  // - The key type (in this case, a string of the form: Somewhere, MA
  // - The type of information embedded within its nodes (the City class)
  // - The type of information embedded within its routes (the Route class)
  Graph<String, City, Route> cities = new Graph<String, City, Route>("United States");

  // A GraphDrawer that draws a Graph<String, City, Route>.
  IGraphTraverser<String, City, Route> draw = new GraphDrawer(0, 300, 0, 300, "Mini Graph", false);
  IGraphTraverser<String, City, Route> drawUSA = new GraphDrawer(125, 65, 50, 30, "USA", true);


  // adds all the links to the cities and adds the cities to the graph
  void setup() {
    // set up the Boston links
    boston.addLink(bostonToTucson);
    boston.addLink(bostonToNewyork);
    boston.addLink(bostonToChicago);

    // set up the Tucson links
    tucson.addLink(tucsonToBoston);
    tucson.addLink(tucsonToChicago);

    // set up the New York
    newyork.addLink(newyorkToBoston);
    newyork.addLink(newyorkToTucson);

    // set up the Chicago
    chicago.addLink(chicagoToNewyork);
    chicago.addLink(chicagoToTucson);

    // set up the Miami
    miami.addLink(miamiToTallahasse);

    // set up the Tallahasse
    tallahasse.addLink(tallahasseToMiami);

    chicagoNode.addLink(chicagoNewyork);
    chicagoNode.addLink(chicagoTucson);
    bostonNode.addLink(bostonTucson);
    bostonNode.addLink(bostonNewyork);
    bostonNode.addLink(bostonChicago);
    tucsonNode.addLink(tucsonBoston);
    tucsonNode.addLink(tucsonChicago);
    newyorkNode.addLink(newyorkBoston);
    newyorkNode.addLink(newyorkChicago);

    // set up path DFS
    pathBostonTucsonDFS.push(this.boston);
    pathBostonTucsonDFS.push(this.tucson);

    pathTucsonNewyorkDFS.push(this.tucson);
    pathTucsonNewyorkDFS.push(this.boston);
    pathTucsonNewyorkDFS.push(this.newyork);

    // set up path BFS
    pathBostonTucsonBFS.add(this.boston);
    pathBostonTucsonBFS.add(this.tucson);

    pathTucsonNewyorkBFS.add(this.tucson);
    pathTucsonNewyorkBFS.add(this.boston);
    pathTucsonNewyorkBFS.add(this.chicago);
    pathTucsonNewyorkBFS.add(this.newyork);

    // set up the graph
    cityGraph.addNode("Boston, MA", boston);
    cityGraph.addNode("Tucson, AZ", tucson);
    cityGraph.addNode("New York, NY", newyork);
    cityGraph.addNode("Chicago, IL", chicago);
    cityGraph.addNode("Miami, FL", miami);
    cityGraph.addNode("Tallahasse, FL", tallahasse);

    cities.addNode("Boston, MA", bostonNode);
    cities.addNode("Tucson, AZ", tucsonNode);
    cities.addNode("New York, NY", newyorkNode);
    cities.addNode("Chicago, IL", chicagoNode);

  }

  // strips all nodes and links from the graph and nodes, respectively.
  void tearDown() {
    cityGraph.clearNodes();
    boston.clearNeighbors();
    tucson.clearNeighbors();
    newyork.clearNeighbors();
    chicago.clearNeighbors();
    miami.clearNeighbors();
    tallahasse.clearNeighbors();

    pathBostonTucsonDFS = new Stack<INode<String, Integer>>();
    pathTucsonNewyorkDFS = new Stack<INode<String, Integer>>();
    pathBostonTucsonBFS = new LinkedList<INode<String, Integer>>();
    pathTucsonNewyorkBFS = new LinkedList<INode<String, Integer>>();

    cities.clearNodes();
    bostonNode.clearNeighbors();
    tucsonNode.clearNeighbors();
    newyorkNode.clearNeighbors();
    chicagoNode.clearNeighbors();
  }

  void testReturnTypes(Tester t) {
    setup();

    t.checkExpect(cityGraph.getNode("Boston, MA"), boston);
    t.checkExpect(cityGraph.getNode("Tucson, AZ"), tucson);
    t.checkExpect(cityGraph.getNode("New York, NY"), newyork);
    t.checkExpect(cityGraph.getNode("Chicago, IL"), chicago);

    t.checkExpect(cityGraph.getNode("Boston, MA").getLink(0), bostonToTucson);
    t.checkExpect(cityGraph.getNode("Boston, MA").getLink(1), bostonToNewyork);
    t.checkExpect(cityGraph.getNode("Chicago, IL").getLink(1), chicagoToTucson);

    tearDown();
  }

  // Tests a drawer.
  void testDrawing(Tester t) {
    setup();
    Scanner in = new Scanner(System.in);
    cities.acceptTraverser(draw);

    // System.out.print("You should see a box with a simple graph. Type 1 and press enter to continue.");
    //int test = in.nextInt();
    //in.close();

    tearDown();
  }

  // Creates a graph and draws it.
  void testUSAGraph(Tester t) {
    Capitals c = new Capitals();
    ArrayList<City> caps = c.makeCapitals();
    ArrayList<String> states = c.makeStates();
    List<List<String>> links = c.neighborlist;

    Graph<String, City, Route> usGraph = GraphGenerator.makeCapitalGraph(caps, states, links);

    usGraph.acceptTraverser(drawUSA);

    Scanner in = new Scanner(System.in);
    System.out.print("You should see a very complex graph. Type 1 and press enter to continue.");
    int test = in.nextInt();
    in.close();

  }

  // Tests a DirectionMaker and PathRoute (and in turn a TraceStrategy)
  void testDirectionMaker(Tester t) throws Exception {
    setup();

    TraceStrategy<City, Route, String> makeDirections = new DirectionMaker();

    ArrayList<INode<City, Route>> samplePath = new ArrayList<INode<City, Route>>();
    samplePath.add(bostonNode);
    samplePath.add(tucsonNode);
    samplePath.add(chicagoNode);
    samplePath.add(newyorkNode);

    PathRoute<City, Route> path = new PathRoute<City, Route>(samplePath);
    t.checkExpect(path.isPathValid(), true);
    t.checkExpect(path.<String>tracePath(makeDirections),
                  path.<String>tracePath(makeDirections));
    //System.out.print(path.<String>tracePath(makeDirections));
    tearDown();
  }
  /* old path data
    void testPathIsValid(Tester t) {
      setup();

      t.checkExpect(pathBostonTucson.isValid(), true);
      t.checkExpect(pathTucsonNewyork.isValid(), true);
      t.checkExpect(pathBostonMiami.isValid(), false);
      t.checkExpect(pathMiamiBoston.isValid(), false);

      tearDown();
    }
  */

  void testAlgorithms(Tester t) {
    setup();

    // DFS
    t.checkExpect(Algorithms.DFS(this.boston, this.tucson).getValue(), pathBostonTucsonDFS);
    t.checkExpect(Algorithms.DFS(this.tucson, this.newyork).getValue(), pathTucsonNewyorkDFS);
    t.checkExpect(Algorithms.DFS(this.boston, this.miami).isSomething(), false);
    t.checkExpect(Algorithms.DFS(this.miami, this.boston).isSomething(), false);

    //BFS
    t.checkExpect(Algorithms.BFS(this.boston, this.tucson).getValue(), pathBostonTucsonBFS);
    t.checkExpect(Algorithms.BFS(this.tucson, this.newyork).getValue(), pathTucsonNewyorkBFS);
    t.checkExpect(Algorithms.BFS(this.boston, this.miami).isSomething(), false);
    t.checkExpect(Algorithms.BFS(this.miami, this.boston).isSomething(), false);

    tearDown();
  }
}
